package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by lyk on 2018-12-21.
 * Package name: leetcode
 * Porject name: untitled1
 */
public class LongPressedName {
    public boolean isLongPressedName(String name, String typed) {
        Group g1 = groupify(name);
        Group g2 = groupify(typed);
        if (!g1.key.equals(g2.key))
            return false;

        for (int i = 0; i < g1.count.size(); ++i)
            if (g1.count.get(i) > g2.count.get(i))
                return false;
        return true;
    }

    public Group groupify(String S) {
        StringBuilder key = new StringBuilder();
        List<Integer> count = new ArrayList();
        int anchor = 0;
        int N = S.length();
        for (int i = 0; i < N; ++i) {
            if (i == N-1 || S.charAt(i) != S.charAt(i+1)) { // end of group
                key.append(S.charAt(i));
                count.add(i - anchor + 1);
                anchor = i+1;
            }
        }

        return new Group(key.toString(), count);
    }
    class Group {
        String key;
        List<Integer> count;
        Group(String k, List<Integer> c) {
            key = k;
            count = c;
        }
    }
    public static void main(String[] args) {
        LongPressedName lpn = new LongPressedName();
        System.out.println(lpn.isLongPressedName("alex", "aaleex"));
        System.out.println(lpn.isLongPressedName("saeed", "ssaaed"));
        System.out.println(lpn.isLongPressedName("leelee", "lleelee"));
    }
}




